import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 * http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15648&pm=12544
 * 
 * @author smarsoll
 * 
 */
public class FragileMirrors2 {

	private static final int END_MIRRORS1 = 30;
	private static final int MAX_NB_BOARD_IN_MEM = 500;
	/** Maximum time 1 in ms. */
	private static final int MAX_TIME_1 = 1000;
	private static final int MAX_TIME_2 = MAX_TIME_1 + 0;
	private Random rnd = new Random(17);
	private static final int NB_BEST_PER_TURN = 1;

	private long startTime;

	private int lowerShots = Integer.MAX_VALUE;
	private BoardState bestFinalBoard = null;
	// private final Comparator<BoardState> compNbMirror = new Comparator<BoardState>() {
	// public int compare(BoardState o1, BoardState o2) {
	// int thisVal = o1.nbMirrors;
	// int anotherVal = o2.nbMirrors;
	// int compare = (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1));
	// if (compare == 0) {
	// thisVal = o1.hashCode();
	// anotherVal = o2.hashCode();
	// compare = (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1));
	// }
	// return compare;
	// }
	// };

	// private SortedSet<BoardState> boardsToInvestigate0 = new TreeSet<BoardState>(compNbMirror);
	private SortedSet<BoardState> boardsToInvestigate0 = new TreeSet<BoardState>();
	private SortedSet<BoardState> boardsToInvestigate1 = new TreeSet<BoardState>();

	// private Set<Integer> allBoardHash = new HashSet<Integer>(10000);
	// private List<BoardState> boardsToInvestigate1 = new LinkedList<BoardState>();
	private int totalNbShots = 0;
	private int boardSize;

	// private BoardState nextBoardToInvestigate = null;

	/**
	 * 
	 * @param board
	 *            {"LLLR", "RLRR", "LLLL", "RRRL"}.
	 * @return {4, 2, -1, 1}.
	 */
	public int[] destroy(String[] board) {
		startTime = System.currentTimeMillis();
		boardSize = board.length;
		log("boardSize=" + boardSize);
		final BoardState field = new BoardState(board);
		List<CellW> lstRays = new ArrayList<FragileMirrors2.CellW>();
		Collection<CellW> possibleRays = getPossibleRays(boardSize);
		field.activeRays = possibleRays;
		field.remainingRays = new HashSet<CellW>(possibleRays);
		field.score = 100.0;
		boardsToInvestigate1.add(field);
		investigate(field, 400, 1);

		// initial fill the boardsToInvestigate sorted set.
		// investigate(field, 400);

		log("==== Starting investigations , boardsToInvestigate.size()=" + boardsToInvestigate0.size() + " " + boardsToInvestigate1.size());
		// investigate while time available
		// BoardState theBoard = getNextBoard();
		long timeSinceSt = timeSinceStart();
		final int endMirrors1 = END_MIRRORS1;
		final int endMirrors2 = 5;
		while (((timeSinceSt < MAX_TIME_2) || bestFinalBoard == null)) {
			timeSinceSt = timeSinceStart();
			Collection<BoardState> theBoards = getNextBoards();
			if (theBoards.isEmpty()) {
				break;
			}
			investigate(theBoards, 300, 1);
			// if (timeSinceSt < MAX_TIME_1) {
			// if (theBoard.nbMirrors > 6000) {
			// investigate(theBoard, 100, 1);
			// } else if (theBoard.nbMirrors > 3000) {
			// investigate(theBoard, 300, 1);
			// } else

			// if (theBoard.nbMirrors <= endMirrors2) {
			// investigate(theBoard, 400, endMirrors2);
			// } else if (theBoard.nbMirrors <= endMirrors1) {
			// investigate(theBoard, 400, 2);
			// } else {
			// investigate(theBoard, 400, 1);
			// }

			// } else {
			// investigate(theBoard, boardSize / 2, 1);
			// }
			// investigate(theBoard, 10, 2);
			// theBoard = getNextBoard();
		}

		// translation for result
		if (bestFinalBoard == null) {
			throw new RuntimeException("no solution found");
		}
		BoardState curBoard = bestFinalBoard;
		CellW[] allRays = new CellW[bestFinalBoard.nbShots];
		int curCell = bestFinalBoard.nbShots;
		while (curBoard.parent != null) {
			curCell--;
			allRays[curCell] = curBoard.rayShot;
			curBoard = curBoard.parent;
		}
		lstRays = Arrays.asList(allRays);

		// translation for result to array
		int[] rays = new int[2 * lstRays.size()];
		int curRay = 0;
		for (CellW cellW : lstRays) {
			rays[curRay * 2] = cellW.r;
			rays[curRay * 2 + 1] = cellW.c;
			curRay++;
		}
		long timeTaken = timeSinceStart();
		log("lstRays.size=" + lstRays.size() + " score " + ((double) boardSize / lstRays.size()) + " , totalNbShots=" + totalNbShots
				+ " , time-taken=" + timeTaken + " per second="
				+ (totalNbShots * 1000.0 / timeTaken));
		return rays;
	}


	private long timeSinceStart() {
		return System.currentTimeMillis() - startTime;
	}

	/**
	 * automatic remove if class0
	 * 
	 * @return
	 */
	private BoardState getNextBoard() {
		if (!boardsToInvestigate0.isEmpty()) {
			BoardState boardState = boardsToInvestigate0.iterator().next();
			boardsToInvestigate0.remove(boardState);
			return boardState;
		} else if (!boardsToInvestigate1.isEmpty()) {
			// return boardsToInvestigate1.get(0);
			return boardsToInvestigate1.first();
		}
		// no more case to investigate
		return null;
	}

	private Collection<BoardState> getNextBoards() {
		Collection<BoardState> result = new ArrayList<BoardState>(NB_BEST_PER_TURN);
		BoardState theBoard;
		while ((theBoard = getNextBoard()) != null && result.size() < NB_BEST_PER_TURN) {
			result.add(theBoard);
		}
		return result;
	}

	private void investigate(Collection<BoardState> theBoards, int maxTries, int depth) {
		for (BoardState boardState : theBoards) {
			investigate(boardState, maxTries, depth);
		}
	}

	private void investigate(BoardState aState, int maxTries, int depth) {
		if (aState.nbShots + 1 < lowerShots) {
			log("========= investigate " + aState + " active rays=" + aState.activeRays.size()
					+ "  boardsToInvestigate.size()="
					+ boardsToInvestigate0.size() + " " + boardsToInvestigate1.size());
			// while (!aState.remainingRays.isEmpty()) {
			// log("new  try");
			Collection<BoardState> bestTests = findASolution(aState, maxTries, depth);
			if (!bestTests.isEmpty()) {
				// keep the best for next turn
				BoardState best = bestTests.iterator().next();
				// log("best is " + best);
				boardsToInvestigate0.add(best);
			}
			// }
			// if (aState.remainingRays.isEmpty()) {
			// removeBoardToInvestigate(aState);
			// }
		} else {
			// this branch is not valuable because a better score is alreadu found
			log("remove " + aState);
			removeBoardToInvestigate(aState);
		}
	}

	private void removeBoardToInvestigate(BoardState aState) {
		// remove in both collections
		// if (!boardsToInvestigate0.remove(aState))
		boardsToInvestigate0.remove(aState);
		boardsToInvestigate1.remove(aState);
	}

	private Collection<BoardState> findASolution(BoardState parentBoard, int maxTries, int depth) {
		// SortedSet<BoardState> bestTests = new TreeSet<BoardState>(compNbMirror);
		SortedSet<BoardState> bestTests = new TreeSet<BoardState>();

		List<CellW> lstRnd = new ArrayList<CellW>(parentBoard.remainingRays);
		if (maxTries < lstRnd.size()) {
			Collections.shuffle(lstRnd, rnd);
		}
		Iterator<CellW> it = lstRnd.iterator();
		// int bestNbMirrorsBroken = Integer.MAX_VALUE;
		// boolean goOn = true;
		int iteration = 0;
		while (it.hasNext()) {
			// test in loop because any sub tree can find a good solution
			if (((parentBoard.nbShots + 1) >= lowerShots)) {
				log("(before) No better solution expected for " + parentBoard);
				removeBoardToInvestigate(parentBoard);
				return bestTests;
			}
			CellW ray = it.next();
			// too much expensive to test all cases
			// if ((iteration == 0) || getProbability()) {
				// remove the ray for future test (but this ray is in children test cases)
				// it.remove();
				parentBoard.remainingRays.remove(ray);

				// try this ray
				BoardState aTest = shootRayAndCheckBoard(parentBoard, ray);

				// keep the best of this turn
				if (aTest != null) {
					bestTests.add(aTest);
					// if (aTest.nbMirrors < bestNbMirrorsBroken) {
					// bestNbMirrorsBroken = aTest.nbMirrors;
					// bestTests.clear();
					// bestTests.add(aTest);
					// } else if (aTest.nbMirrors < bestNbMirrorsBroken + 2) {
					// // keep it as a parallel branch to investigate
					// bestTests.add(aTest);
					// }
				// Depth exploration
				if (depth > 1) {
					bestTests.addAll(findASolution(aTest, maxTries, depth - 1));
				}

				// if (bestTests.size() >= maxTries) {
				// break;
				// }
				}

			// }

			iteration++;
			if (iteration >= maxTries) {
				break;
			}
		}
		it = null;
		// we should have explore all rays execpt because of end time processing with proba
		if (parentBoard.remainingRays.isEmpty()) {
			removeBoardToInvestigate(parentBoard);
		}
		// keep best and best - 1
		if (!bestTests.isEmpty()) {
			// int bestNbMirrors = bestTests.first().nbMirrors;
			// if (bestNbMirrors <= parentBoard.bestChildNbMirrors) {
			// parentBoard.bestChildNbMirrors = bestNbMirrors;
			//
			// } else {
			// // we did not find better solution for these tries
			// bestNbMirrors = parentBoard.bestChildNbMirrors;
			// }
			// // remove the ones that are far from best
			// Iterator<BoardState> itBoard = bestTests.iterator();
			// while (itBoard.hasNext()) {
			// if (itBoard.next().nbMirrors > bestNbMirrors + (bestNbMirrors / 100)) {
			// itBoard.remove();
			// }
			// }
			addBoardsToInvestigate(bestTests);
		}
		return bestTests;
	}

	private void addBoardsToInvestigate(Collection<BoardState> bestTests) {
		Iterator<BoardState> it = bestTests.iterator();
		// the first
		// if (it.hasNext()) {
		// BoardState firstBoard = it.next();
		// // boardsToInvestigate0.add(firstBoard);
		// boardsToInvestigate1.add(firstBoard);
		// // checkHash(firstBoard);
		// }
		// the others
		int nbAdded = 0;
		while (it.hasNext()) {
			BoardState aBoard = it.next();
			if (nbAdded < NB_BEST_PER_TURN) {
				boardsToInvestigate0.add(aBoard);
				log("boardsToInvestigate0.add " + aBoard);
			}
			boardsToInvestigate1.add(aBoard);
			nbAdded++;
			// checkHash(firstBoard);
		}
		while (boardsToInvestigate0.size() > NB_BEST_PER_TURN) {
			boardsToInvestigate0.remove(boardsToInvestigate0.last());
		}
		while (boardsToInvestigate1.size() > MAX_NB_BOARD_IN_MEM) {
			boardsToInvestigate1.remove(boardsToInvestigate1.last());
		}
	}

	// private void checkHash(BoardState board) {
	// if (!allBoardHash.add(board.calculateHash())) {
	// logErr("it was already added " + board);
	// }
	// }
	//
	// private boolean getProbability() {
	// long startedTime = (System.currentTimeMillis() - startTime);
	// if (startedTime <= MAX_TIME_1) {
	// return true;
	// }
	// int total = 1 + (int) (20 * (startedTime - MAX_TIME_1)) / (MAX_TIME_2 - MAX_TIME_1);
	// // log("total=" + total);
	// return rnd.nextInt(total) == 0;
	// }

	private BoardState shootRayAndCheckBoard(BoardState parentBoard, CellW ray) {
		// if (!((parentBoard.nbShots + 1) < lowerShots)) {
		// log("(before) No better solution expected for " + parentBoard);
		// removeBoardToInvestigate(parentBoard);
		// return null;
		// }
		// log("findASolution on " + parentBoard.nbShots);
		BoardState aTest = new BoardState(parentBoard);
		int nbShot = aTest.shootRay(ray);
		totalNbShots++;

		// remove the ray for future test (but this ray is in children test cases)
		// parentBoard.remainingRays.remove(ray); => done by caller

		if (nbShot == 0) {
			// remove the ray because no more mirrors on this line
			// log("nbShot == 0");
			// parentBoard.activeRays.remove(ray);
			// parentBoard.activeRays.remove(getOppositeRay(ray));
			return null;
		} else {
			if (aTest.nbMirrors == 0) {
				// this is a final shoot, is it the best ?
				if (aTest.nbShots < lowerShots) {
					log("     ============ a new better found for " + aTest + " at ms " + timeSinceStart());
					setBestFinalBoard(aTest);
					return aTest;
				} else {
					log("nbMirrors == 0 but not better " + aTest);
				}

			} else {
				// we can try again if we expect better (+1 to consider next turn)
				if ((aTest.nbShots + 1) < lowerShots) {
					int shotsDistance = lowerShots - aTest.nbShots;
					if ((shotsDistance < 2000) && (aTest.nbMirrors > END_MIRRORS1)
							&& ((double) aTest.score > allBoards[aTest.nbShots - 1].score * 1.4)) {
						// logErr("Give up branch at " + shotsDistance + " for " + aTest);
						return null;
					}

					// good shot to be investigated
					return aTest;
				} else {
					// throw new RuntimeException("");
					// log("No better solution expected for " + aTest.nbShots);
					return null;
				}
			}
		}
		return null;
	}

	// private void addBoardToInvestigate(SortedSet<BoardState> setOfBoards, BoardState aTest) {
	// setOfBoards.add(aTest);
	// // memory optimisation : remove bad score
	// if (setOfBoards.size() > MAX_NB_BOARD_IN_MEM) {
	// setOfBoards.remove(setOfBoards.last());
	// }
	// }

	private CellW getOppositeRay(CellW ray) {
		if (ray.r == -1) {
			return new CellW(boardSize, ray.c);
		}
		if (ray.r == boardSize) {
			return new CellW(-1, ray.c);
		}
		if (ray.c == -1) {
			return new CellW(ray.r, boardSize);
		}
		if (ray.c == boardSize) {
			return new CellW(ray.r, -1);
		}
		throw new RuntimeException("not implemented");
		// return null;
	}

	private BoardState[] allBoards;
	private void setBestFinalBoard(BoardState aTest) {
		lowerShots = aTest.nbShots;
		bestFinalBoard = aTest;
		BoardState curBoard = aTest;
		allBoards = new BoardState[aTest.nbShots];
		int curCell = aTest.nbShots;
		while (curBoard.parent != null) {
			curCell--;
			allBoards[curCell] = curBoard;
			curBoard = curBoard.parent;
		}
	}

	private Collection<CellW> getPossibleRays(int boardSize) {
		List<CellW> lstRays = new ArrayList<CellW>();
		int middle = boardSize / 2;
		boolean impair = middle * 2 != boardSize;
		if (impair) {
			// cas impair (ex 5 => 2)
			add4Cells(boardSize, lstRays, middle);
		}
		for (int i = 0; i < middle; i++) {
			add4Cells(boardSize, lstRays, middle - i - 1);
			if (impair) {
				add4Cells(boardSize, lstRays, middle + i + 1);
			} else {
				add4Cells(boardSize, lstRays, middle + i);
			}
		}
		// Collections.shuffle(lstRays, rnd);
		return lstRays;
	}

	private void add4Cells(int boardSize, List<CellW> lstRays, int i) {
		lstRays.add(new CellW(-1, i));
		lstRays.add(new CellW(boardSize, i));
		lstRays.add(new CellW(i, -1));
		lstRays.add(new CellW(i, boardSize));
	}

	private void log(String string) {
		System.out.println(string);
	}

	private void logErr(String string) {
		System.err.println(string);
	}

	class CellW {
		int r, c;

		@Override
		public int hashCode() {
			return r + (c * 10001);
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			CellW other = (CellW) obj;
			// if (!getOuterType().equals(other.getOuterType()))
			// return false;
			if (c != other.c)
				return false;
			if (r != other.r)
				return false;
			return true;
		}

		public CellW(int r, int c) {
			this.r = r;
			this.c = c;
		}

		private FragileMirrors2 getOuterType() {
			return FragileMirrors2.this;
		}
	}

	class BoardState implements Comparable<BoardState> {
		private static final char RIGHT = 'R';
		private static final char LEFT = 'L';
		private static final char SPACE = ' ';

		@Override
		public String toString() {
			return "BoardState [shots=" + nbShots + ", sc=" + score + " " + nbMirrors + " " + conRate + "]";
		}

		final int[] DR = new int[] { -1, 0, 1, 0 };
		final int[] DC = new int[] { 0, 1, 0, -1 };

		final int[] LL = new int[] { 1, 0, 3, 2 };
		final int[] RR = new int[] { 3, 2, 1, 0 };

		final int N;
		int nbMirrors;
		int bestChildNbMirrors = Integer.MAX_VALUE;
		int nbShots = 0;
		char[][] what;
		// Map<CellW, Character> mirrors;

		/** The rays not yet tested. */
		Collection<CellW> remainingRays;
		/** The rays that have mirrors on their sight. */
		Collection<CellW> activeRays;
		BoardState parent = null;
		private CellW rayShot = null;
		double score = 0.0;
		private double conRate;

		// private int calculateHash() {
		// StringBuilder sb = new StringBuilder(N * N);
		// for (char[] aLine : what) {
		// sb.append(aLine);
		// }
		// return sb.toString().hashCode();
		// }

		public BoardState(String[] board) {
			this.N = board.length;
			this.nbMirrors = N * N;
			this.what = new char[N][];
			for (int i = 0; i < N; i++) {
				this.what[i] = board[i].toCharArray();
			}
			// this.mirrors = new HashMap<CellW, Character>(nbMirrors);
			// for (int row = 0; row < N; row++) {
			// for (int col = 0; col < N; col++) {
			// mirrors.put(new CellW(row, col), board[row].charAt(col));
			// }
			// }
		}

		// private void shootRay(List<CellW> curRays) {
		// for (CellW ray : curRays) {
		// shootRay(ray);
		// }
		// }

		public BoardState(BoardState tpl) {
			this.parent = tpl;
			this.nbShots = tpl.nbShots + 1;
			this.N = tpl.N;
			this.nbMirrors = tpl.nbMirrors;
			this.what = tpl.what.clone();
			for (int i = 0; i < tpl.what.length; i++) {
				this.what[i] = tpl.what[i].clone();
			}
			// this.mirrors = new HashMap<CellW, Character>(tpl.mirrors);
			// new set to remove rays
			// this.remainingRays = new HashSet<FragileMirrors.CellW>(tpl.activeRays);
			// this.activeRays = new HashSet<FragileMirrors.CellW>(tpl.activeRays);
		}

		private int shootRay(CellW ray) {
			rayShot = ray;
			int r = ray.r, c = ray.c;
			if (r == -1 && c >= 0 && c < N) {
				return shootRay(ray, 2);
			} else if (r == N && c >= 0 && c < N) {
				return shootRay(ray, 0);
			} else if (c == -1 && r >= 0 && r < N) {
				return shootRay(ray, 1);
			} else if (c == N && r >= 0 && r < N) {
				return shootRay(ray, 3);
			} else {
				System.err.println("in ERROR: ray " + " (0-based) starts at an invalid point (row " + r + ", column " + c + ").");
				return -1;
			}
		}

		private int shootRay(CellW ray, int d) {
			int r = ray.r, c = ray.c;
			int curR = r;
			int curC = c;
			int curD = d;

			int nbMirrorsForthisShot = 0;
			// List<CellW> res = new ArrayList<CellW>();
			// res.add(new CellW(curR, curC));
			curR += DR[curD];
			curC += DC[curD];

			while (curR >= 0 && curR < N && curC >= 0 && curC < N) {
				// CellW curCell = new CellW(curR, curC);
				// Character curMirror = mirrors.get(curCell);
				if (what[curR][curC] == LEFT || what[curR][curC] == RIGHT) {
					// if (curMirror != null) {
					// res.add(new CellW(curR, curC));
					curD = (what[curR][curC] == LEFT ? LL[curD] : RR[curD]);
					// curD = (curMirror == LEFT ? LL[curD] : RR[curD]);
					// what[curR][curC] = (what[curR][curC] == 'L' ? 'l' : 'r');
					what[curR][curC] = SPACE;
					// mirrors.remove(curCell);
					nbMirrors--;
					nbMirrorsForthisShot++;
				}
				curR += DR[curD];
				curC += DC[curD];
			}
			this.calcScore();
			// log(this.toString());
			// res.add(new CellW(curR, curC));
			return nbMirrorsForthisShot;
		}

		private void calcScore() {
			int[] minRows = new int[N];
			int[] minCols = new int[N];
			for (int row = 0; row < N; row++) {
				for (int col = 0; col < N; col++) {
					if (what[row][col] != SPACE) {
						// rows.add(row);
						// cols.add(col);
						minRows[row]++;
						minCols[col]++;
					}
				}
			}
			activeRays = new ArrayList<CellW>(N * 2);
			int nbLines = 0;
			for (int i = 0; i < N; i++) {
				if (minRows[i] > 0) {
					activeRays.add(new CellW(i, -1));
					activeRays.add(new CellW(i, boardSize));
					nbLines++;
					// minLineOccupation = Math.min(minLineOccupation, minRows[i]);
				}
				if (minCols[i] > 0) {
					activeRays.add(new CellW(-1, i));
					activeRays.add(new CellW(boardSize, i));
					nbLines++;
					// minLineOccupation = Math.min(minLineOccupation, minCols[i]);
				}
			}
			this.remainingRays = new HashSet<CellW>(activeRays);
			score = nbMirrors + nbShots;
		}

		private void calcScore2() {
			// for the "remplissage" rate
			// HashSet<Integer> rows = new HashSet<Integer>(N);
			// HashSet<Integer> cols = new HashSet<Integer>(N);
			// nb isolated
			int nbIsolated = 0;
			int[] minRows = new int[N];
			int[] minCols = new int[N];
			int totNbConnections = 0;
			HashSet<CellW> theCells = new HashSet<CellW>(N + 100);
			Map<Integer, Collection<CellW>> cols = new HashMap<Integer, Collection<CellW>>();
			Map<Integer, Collection<CellW>> rows = new HashMap<Integer, Collection<CellW>>();
			for (int row = 0; row < N; row++) {
				for (int col = 0; col < N; col++) {
					if (what[row][col] != SPACE) {
						CellW cell = new CellW(row, col);
						theCells.add(cell);
						getList(cols, col).add(cell);
						getList(rows, row).add(cell);
						int nbConnections = getNbConnections(row, col);
						if (nbConnections > 0) {
							totNbConnections += nbConnections;
						} else if (isIsolated(row, col)) {
							nbIsolated++;
						}
						// rows.add(row);
						// cols.add(col);
						minRows[row]++;
						minCols[col]++;
					}
				}
			}
			int nbPackets = 0;
			while (!cols.isEmpty()) {
				// CellW cell = theCells.iterator().next();
				// theCells.remove(cell);
				Entry<Integer, Collection<CellW>> entry = cols.entrySet().iterator().next();
				cols.remove(entry.getKey());
				// removeConnected(cols, rows, entrySet.getValue(), true);
				removeConnectedRows(rows, cols, entry.getValue());
				// removeConnected(theCells, cell, true);
				// removeConnected(theCells, cell, false);
				nbPackets++;
			}
			if (nbPackets > 1) {
				log("nbPackets=" + nbPackets);
			}

			conRate = 2.0 * nbMirrors / (totNbConnections + 1);
			// logErr("conRate=" + conRate);
			// for (CellW aMirror : mirrors.keySet()) {
			// rows.add(aMirror.r);
			// cols.add(aMirror.c);
			// // minRows[aMirror.r]++;
			// // minCols[aMirror.c]++;
			// }
			// int minLineOccupation = Integer.MAX_VALUE;
			// update rays
			activeRays = new ArrayList<CellW>(N * 2);
			int nbLines = 0;
			for (int i = 0; i < N; i++) {
				if (minRows[i] > 0) {
					activeRays.add(new CellW(i, -1));
					activeRays.add(new CellW(i, boardSize));
					nbLines++;
					// minLineOccupation = Math.min(minLineOccupation, minRows[i]);
				}
				if (minCols[i] > 0) {
					activeRays.add(new CellW(-1, i));
					activeRays.add(new CellW(boardSize, i));
					nbLines++;
					// minLineOccupation = Math.min(minLineOccupation, minCols[i]);
				}
			}
			// logErr("minLineOccupation=" + minLineOccupation);

			// for (Integer integer : rows) {
			// activeRays.add(new CellW(integer, -1));
			// activeRays.add(new CellW(integer, boardSize));
			// }
			// for (Integer integer : cols) {
			// activeRays.add(new CellW(-1, integer));
			// activeRays.add(new CellW(boardSize, integer));
			// }
			this.remainingRays = new HashSet<CellW>(activeRays);

			// if (nbIsolated > 0) {
			// logErr("nbIsolated=" + nbIsolated);
			// }
			// 0,60 to 0,62
			// score = nbMirrors * nbShots * nbShots;

			// 0,66
			// score = (nbMirrors + 4 * nbIsolated) * nbShots * nbShots;

			// 0,68 0,69
			// score = (nbMirrors + rows.size() + cols.size()) * nbShots * nbShots;
			// 0,68 0,69, 0,73
			// score = conRate * ((double) nbMirrors + 4 * (nbLines)) * Math.pow(nbShots + 2, 1.8);
			// score = (conRate * nbMirrors + 4 * nbIsolated) * Math.pow(nbShots + 2, 1.8);

			score = conRate * nbMirrors + 2 * (nbPackets) + nbShots;

			// score = ((double) nbMirrors + 1.0 * (rows.size() * cols.size())) * nbShots * nbShots;
			// score = ((double) nbMirrors) * nbShots * nbShots / rows.size() / cols.size();

			// score = (nbMirrors + 2 * nbIsolated + 2 * (rows.size() + cols.size())) * nbShots * nbShots;

			// score = (N * N - nbMirrors - (nbIsolated)) / (double) this.nbShots;
			// score = (N * N - nbMirrors);
			// score = (N * N - nbMirrors) / Math.pow(this.nbShots, 0.5);
			// score = (N * N - nbMirrors - (2 * nbIsolated) - rows.size() - cols.size()) / Math.pow(this.nbShots, 1.4);
			// score = (nbMirrors + 2 * nbIsolated + 0.5 * (rows.size() * cols.size()));// * Math.pow(this.nbShots,
			// 1.0);
			// score = (N * N - nbMirrors - (2 * nbIsolated)) / Math.pow(this.nbShots, 1.4);
			// score = (N * N - nbMirrors) / Math.log10(this.nbShots + 1);
			// if (activeRays.size() < 204) {
			// logErr("activeRays.size()=" + activeRays.size() + " for " + this);
			// }

		}

		private void removeConnectedRows(Map<Integer, Collection<CellW>> rows, Map<Integer, Collection<CellW>> cols,
				Collection<CellW> value) {
			for (CellW cellW : value) {
				Collection<CellW> rowRemoved = rows.remove(cellW.r);
				if (rowRemoved != null) {
					removeConnectedCols(rows, cols, rowRemoved);
				}
			}

		}

		private void removeConnectedCols(Map<Integer, Collection<CellW>> rows, Map<Integer, Collection<CellW>> cols,
				Collection<CellW> value) {
			for (CellW cellW : value) {
				Collection<CellW> colRemoved = cols.remove(cellW.c);
				if (colRemoved != null) {
					removeConnectedRows(rows, cols, colRemoved);
				}
			}

		}

		private void removeConnected(Map<Integer, Collection<CellW>> cols, Map<Integer, Collection<CellW>> rows, Collection<CellW> value,
				boolean isCol) {
			// TODO Auto-generated method stub

		}

		private Collection<CellW> getList(Map<Integer, Collection<CellW>> cols, int col) {
			Collection<CellW> result = cols.get(col);
			if (result == null) {
				result = new ArrayList<CellW>();
				cols.put(col, result);
			}
			return result;
		}

		// private void removeConnected(HashSet<CellW> theCells, CellW curCell, boolean isRow) {
		// // theCells.remove(curCell);
		// for (Iterator<CellW> iterator = theCells.iterator(); iterator.hasNext();) {
		// CellW cellW = iterator.next();
		// // for (CellW cellW : theCells) {
		// if (isRow) {
		// if (cellW.r == curCell.r) {
		// iterator.remove();
		// removeConnected(theCells, cellW, !isRow);
		// }
		// } else {
		// if (cellW.c == curCell.c) {
		// iterator.remove();
		// removeConnected(theCells, cellW, !isRow);
		// }
		// }
		// }
		// }

		/** Check isolation. */
		private boolean isIsolated(int row, int col) {
			// if (what[row][col] == SPACE) {
			// return false;
			// }
			for (int ri = 0; ri < row; ri++) {
				if (what[ri][col] != SPACE) {
					return false;
				}
			}
			for (int ri = row + 1; ri < N; ri++) {
				if (what[ri][col] != SPACE) {
					return false;
				}
			}
			for (int ci = 0; ci < col; ci++) {
				if (what[row][ci] != SPACE) {
					return false;
				}
			}
			for (int ci = col + 1; ci < N; ci++) {
				if (what[row][ci] != SPACE) {
					return false;
				}
			}
			// we did not find any L or R
			return true;
		}
		private int getNbConnections(int row, int col) {
			int nbCon = 0;
			for (int ri = 0; ri < row; ri++) {
				if (what[ri][col] != SPACE) {
					nbCon++;
					break;
				}
			}
			// for (int ri = row + 1; ri < N; ri++) {
			// if (what[ri][col] != SPACE) {
			// nbCon++;
			// break;
			// }
			// }
			for (int ci = 0; ci < col; ci++) {
				if (what[row][ci] != SPACE) {
					nbCon++;
					break;
				}
			}
			// for (int ci = col + 1; ci < N; ci++) {
			// if (what[row][ci] != SPACE) {
			// nbCon++;
			// break;
			// }
			// }
			return nbCon;
		}

		public int compareTo(BoardState other) {
			// return Double.compare(this.score, other.score);
			// reverse to have best score in first position
			int scoreCompare = Double.compare(this.score, other.score);
			// if (scoreCompare == 0) {
			// int thisVal = this.hashCode();
			// int anotherVal = other.hashCode();
			// return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1));
			// }
			return scoreCompare;
		}

	}

}
